package com.jia.leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-09 13:04
 */
public class Pro5485 {
    /**
     * 1.利用前缀和+hash  求出preIndex[j] 第i个数字到j个数字的和为target
     * 2.利用preIndex数组，动态规划求最大不覆盖子数组为target的最大个数
     * @param nums
     * @param target
     * @return
     */
    public int maxNonOverlapping(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();//<sum,index>
        map.put(0, 0);
        int[] dp = new int[nums.length + 1];
        for(int i = 1, sum = 0; i <= nums.length; i++) {
            sum += nums[i-1];
            if(map.containsKey(sum - target)) {
                dp[i] = Math.max(dp[i-1], dp[map.get(sum - target)] + 1);
            }else {
                dp[i] = dp[i-1];
            }
            map.put(sum, i);
        }
        return dp[nums.length];
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1};
        int target = 2;


        Pro5485 pro5485 = new Pro5485();
        pro5485.maxNonOverlapping(nums, target);
    }
}
